230. 二叉搜索树中第K小的元素

Similar Question

leading to the advanced question

Solution Tips

方案一: 中序迭代

迭代法可以提前退出, 不用遍历全部节点

var kthSmallest = function(root, k) {
    // 迭代中序试试

    const queue = [root];
    let cur = root;
    let index = 0;

    while (cur || queue.length) {
        while (cur) {
            queue.push(cur);
            cur = cur.left;
        }

        cur = queue.pop();
        index++;
        if (index === k) return cur.val;
        cur = cur.right;
    }

    return;
};

方法二: 记录子树的节点数

本质上就是利用了 BST 的性质

var kthSmallest = function(root, k) {
    const bst = new MyBst(root);
    return bst.kthSmallest(k);
};

class MyBst {
    constructor(root) {
        this.root = root;
        this.nodeNum = new Map();
        this.countNode(root);
    }

    // 返回二叉搜索树中第k小的元素
    kthSmallest(k) {
        let node = this.root;
        while (node != null) {
            const left = this.getNodeNum(node.left);
            if (left < k - 1) {
                node = node.right;
                // 在右子树寻找, 需要减去所有比右子树 root 小的元素
				// 与单纯的递归法思路类似
                k = k - (left + 1);
            } else if (left === k - 1) {
                break;
            } else {
                node = node.left;
            }
        }
        return node.val;
    }

    /**
     * 统计以node为根结点的子树的结点数
     */
    countNode(node) {
        if (node == null) {
            return 0;
        }
        this.nodeNum.set(node, 1 + this.countNode(node.left) + this.countNode(node.right));
        return this.nodeNum.get(node);
    }

    /**
     * 统计以node为根结点的子树的结点数
     */
    getNodeNum(node) {
        return this.nodeNum.get(node) || 0;
    }
}

方案三: AVL 数 Search Top K

法 2 可以理解成是法 3 的前置知识。因为是要搭配使用的。在常见的业务要求增删改查都要的话。法 2 + 法 3 配合使用就全是 logn 级别的复杂度。数组的增删复杂度高。也是树形结构本身的优点来的。